/*
    FreeRTOS V9.0.0 - Copyright (C) 2016 Real Time Engineers Ltd.
    All rights reserved

    VISIT http://www.FreeRTOS.org TO ENSURE YOU ARE USING THE LATEST VERSION.

    This file is part of the FreeRTOS distribution.

    FreeRTOS is free software; you can redistribute it and/or modify it under
    the terms of the GNU General Public License (version 2) as published by the
    Free Software Foundation >>>> AND MODIFIED BY <<<< the FreeRTOS exception.

    ***************************************************************************
    >>!   NOTE: The modification to the GPL is included to allow you to     !<<
    >>!   distribute a combined work that includes FreeRTOS without being   !<<
    >>!   obliged to provide the source code for proprietary components     !<<
    >>!   outside of the FreeRTOS kernel.                                   !<<
    ***************************************************************************

    FreeRTOS is distributed in the hope that it will be useful, but WITHOUT ANY
    WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
    FOR A PARTICULAR PURPOSE.  Full license text is available on the following
    link: http://www.freertos.org/a00114.html

    ***************************************************************************
     *                                                                       *
     *    FreeRTOS provides completely free yet professionally developed,    *
     *    robust, strictly quality controlled, supported, and cross          *
     *    platform software that is more than just the market leader, it     *
     *    is the industry's de facto standard.                               *
     *                                                                       *
     *    Help yourself get started quickly while simultaneously helping     *
     *    to support the FreeRTOS project by purchasing a FreeRTOS           *
     *    tutorial book, reference manual, or both:                          *
     *    http://www.FreeRTOS.org/Documentation                              *
     *                                                                       *
    ***************************************************************************

    http://www.FreeRTOS.org/FAQHelp.html - Having a problem?  Start by reading
    the FAQ page "My application does not run, what could be wrong?".  Have you
    defined configASSERT()?

    http://www.FreeRTOS.org/support - In return for receiving this top quality
    embedded software for free we request you assist our global community by
    participating in the support forum.

    http://www.FreeRTOS.org/training - Investing in training allows your team to
    be as productive as possible as early as possible.  Now you can receive
    FreeRTOS training directly from Richard Barry, CEO of Real Time Engineers
    Ltd, and the world's leading authority on the world's leading RTOS.

    http://www.FreeRTOS.org/plus - A selection of FreeRTOS ecosystem products,
    including FreeRTOS+Trace - an indispensable productivity tool, a DOS
    compatible FAT file system, and our tiny thread aware UDP/IP stack.

    http://www.FreeRTOS.org/labs - Where new FreeRTOS products go to incubate.
    Come and try FreeRTOS+TCP, our new open source TCP/IP stack for FreeRTOS.

    http://www.OpenRTOS.com - Real Time Engineers ltd. license FreeRTOS to High
    Integrity Systems ltd. to sell under the OpenRTOS brand.  Low cost OpenRTOS
    licenses offer ticketed support, indemnification and commercial middleware.

    http://www.SafeRTOS.com - High Integrity Systems also provide a safety
    engineered and independently SIL3 certified version for use in safety and
    mission critical applications that require provable dependability.

    1 tab == 4 spaces!
*/


#include <stdlib.h>
#include "FreeRTOS.h"
#include "list.h"

/*-----------------------------------------------------------
 * PUBLIC LIST API documented in list.h
 *----------------------------------------------------------*/
//列表初始化
void vListInitialise( List_t * const pxList )
{
	/*将链表索引指针指向最后一个节点，也就是第0个节点*/
	pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd );

	/* 将最后一个节点的辅助排序值设置为最大，确保该节点就是链表的最后一个节点*/
	pxList->xListEnd.xItemValue = portMAX_DELAY;

	/*将最后一个节点的前序节点和后驱节点指向自己，表示链表为空*/
	pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );	/*lint !e826 !e740 The mini list structure is used as the list end to save RAM.  This is checked and valid. */
	pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );/*lint !e826 !e740 The mini list structure is used as the list end to save RAM.  This is checked and valid. */

    /*初始化链表节点计数器的值为0*/
	pxList->uxNumberOfItems = ( UBaseType_t ) 0U;

	/* Write known values into the list if
	configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
	listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );
	listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );
}
/*-----------------------------------------------------------*/
// 链表节点初始化
void vListInitialiseItem( ListItem_t * const pxItem )
{
	/*初始化该节点所在链表为NULL*/
	pxItem->pvContainer = NULL;

	/* Write known values into the list item if
	configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
	listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
	listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
}

/*-----------------------------------------------------------*/
//将节点插入链表尾部
void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )
{
	// 存下这个链表的索引指针
	ListItem_t * const pxIndex = pxList->pxIndex;

	listTEST_LIST_INTEGRITY( pxList );
	listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );

	/* 插入新节点 */
	pxNewListItem->pxNext = pxIndex;
	pxNewListItem->pxPrevious = pxIndex->pxPrevious;

	mtCOVERAGE_TEST_DELAY();
	
    /* 双向连接 */
	pxIndex->pxPrevious->pxNext = pxNewListItem;
	pxIndex->pxPrevious = pxNewListItem;

	/* 记住该节点所在的链表. */
	pxNewListItem->pvContainer = ( void * ) pxList;

    /* 链表计数器++ */
	( pxList->uxNumberOfItems )++;
}
/*-----------------------------------------------------------*/
//节点按照升序插入链表
void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )
{
	//迭代器设计模式
	ListItem_t *pxIterator;
	//获取节点的排序辅助值
	const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;

	listTEST_LIST_INTEGRITY( pxList );
	listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );

	/* 根据节点的排序辅助值，寻找节点要插入的位置，如果是最大值，那么直接插入最后一个节点的前一个就是了*/
	if( xValueOfInsertion == portMAX_DELAY )
	{
		pxIterator = pxList->xListEnd.pxPrevious;
	}
	//否则不断向前遍历
	else
	{
		// 当迭代器的下一个节点中的排序辅助值小于当前节点的排序辅助值时,迭代器迭代到它的下一个节点
		for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd ); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext ) /*lint !e826 !e740 The mini list structure is used as the list end to save RAM.  This is checked and valid. */
		{
			/* There is nothing to do here, just iterating to the wanted
			insertion position. */
		}
	}
	//经历完上面的for循环后，迭代器所指向的就已经是升序插入的位置了，这里进行插入
	pxNewListItem->pxNext = pxIterator->pxNext;
	pxNewListItem->pxNext->pxPrevious = pxNewListItem;
	pxNewListItem->pxPrevious = pxIterator;
	pxIterator->pxNext = pxNewListItem;
	/* 记住该节点所在的链表. */
	pxNewListItem->pvContainer = ( void * ) pxList;
    /* 链表计数器++ */
	( pxList->uxNumberOfItems )++;
}
/*-----------------------------------------------------------*/
//从链表中移除节点
UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
{
	//获取节点所在的链表
	List_t * const pxList = ( List_t * ) pxItemToRemove->pvContainer;
	//移除
	pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
	pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;

	mtCOVERAGE_TEST_DELAY();

	/* 如果移除的节点位置就是链表的索引指针位置，那么要前移，确保链表的索引指针指向有效的节点 */
	if( pxList->pxIndex == pxItemToRemove )
	{
		pxList->pxIndex = pxItemToRemove->pxPrevious;
	}
	else
	{
		mtCOVERAGE_TEST_MARKER();
	}
	//初始化该节点所在的链表为空
	pxItemToRemove->pvContainer = NULL;
	//链表节点计数器--
	( pxList->uxNumberOfItems )--;
	//返回链表中剩余的节点个数
	return pxList->uxNumberOfItems;
}
/*-----------------------------------------------------------*/

